This invention relates to a method and apparatus for carrying out a dithering operation.
Several types of imaging devices, i.e. devices for creating a visible image in response to an electrical signal, simulate a spatially continuous image as a rectangular array of discrete pixels. One such imaging device is the cathode ray tube display device. In the case of a cathode ray tube display device, the intensity with which a given pixel is illuminated is continuously variable and therefore a continuous tone image can be rendered. The ink-jet printer on the other hand, is a bi-level imaging device, in that each pixel is either stimulated, by printing a dot, or is not stimulated, so that no ink is applied and the paper is left white at that pixel position. The liquid crystal display device is a bi-level imaging device in which each pixel either reflects or absorbs incident light.
Ordered dithering is used to enable a continuous tone image to be rendered by use of a bilevel imaging device. In a conventional ordered dithering operation, a continuous tone image is sampled uniformly in two mutually perpendicular directions to provide a rectangular array of pixel values. A rectangular half-tone screen provides a threshold value for each pixel, and each pixel value is compared with the corresponding threshold value. If the pixel value is greater than the threshold value, a dot is printed for that pixel, and otherwise the paper is left white.
The half-tone screen may be organized as a magic square, which is a square array of numbers such that each column, each row and the two major diagonals produce the same sum. The screen is repeated over the array of pixel values without overlapping, so that one threshold value is associated with each pixel value. A 16.times.16 magic square is shown in FIG. 1. If the image is composed of an array of 1024.times.1024 pixels, the 16.times.16 magic square is repeated 4096 times over the image.
The magic square shown in FIG. 1 is a rectangular array of numbers from 0 to 255. It will be understood by those skilled in the art that such a magic square would be used for carrying out a dithering operation on a sequence of pixel values that can be expressed by numbers in the range from 0 to 255, e.g. an eight-bit digital signal. If a given pixel value is mapped to a cell of the magic square for which the number is less than the pixel value, a dot is applied to the paper, otherwise no dot is applied to the paper.
The conventional ordered dithering operation is subject to disadvantage, in that it is not well-suited to the rendering of edges of relatively low contrast. Whether an edge is detected by a half-tone screen depends on the amplitude, or contrast, of the edge and on the orientation of the edge relative to the screen. For example, FIG. 1 illustrates lines connecting the numbers 0, 1, 2, 3 (increments of 1); 0, 4, 8, 12 (increments of 4); 7, 23, 39, 55 (16); and 13, 77, 141, 205 (64). The significance of these groups of numbers is that the distance between the numbers indicates the frequency with which the contrast value represented by the increment is sampled. Assuming that the horizontal and vertical spacings between adjacent numbers are equal to one, the distance between the numbers 0 and 4 is equal to 8.94 whereas the distance between the numbers 4 and 8 is equal to 8. The distance between the numbers 7 and 23 is 2.24 and the distance between 23 and 39 is 2. Thus, the contrast value of 4 is sampled at a frequency (1/8.94)fs, where fs is the spatial frequency at which the image is sampled, or (1/8)fs, depending on the sampling direction, and the contrast value 16 is sampled at a frequency (1/2.24)fs or (1/2)fs, depending on the sampling direction.
Attempts have been made to overcome this disadvantage of the ordered dithering operation by designing adaptive ordered dithering schemes. Attention is directed in this regard to D. Anastassiou and K. Pennington "Digital Half-Toning of Images", IBM Journal of Research and Development, Vol. 26, No. 6, November 1982, 687; P. Roetling "Half-Tone Method with Edge Enhancement and Moire Suppression", Journal of the Optical Society of America, Vol. 66, No. 10, October 1976, 985, J. White "Systems Approach for Bilevel Printer/Display Thresholding with Resolution Translation", SID 80 Digest, 94, and S. Yoshida, M. Itoh, N. Umebara and H. Sakamoto "High Resolution Thermal Ink Transfer Color Printer", SID 85 Digest, 140. These adaptive schemes are themselves subject to disadvantage, however, in that they are computationally intensive or are not suitable for use with color pictures. Moreover, the adaptive schemes do not use the properties of the half-tone screen in the frequency domain. Such properties have long been established to have a significant influence on image quality.